package main

import (
	"fmt"
	"sort"
)

func main() {
	fmt.Println(combinationSum2([]int{1, 1, 2}, 3))
}

// 实现方式1
func combinationSum2(candidates []int, target int) [][]int {
	var res [][]int
	var list []int
	var helper func(target int, index int)
	sort.Ints(candidates)
	helper = func(target int, index int) {
		if target == 0 {
			tmp := make([]int, len(list))
			copy(tmp, list)
			res = append(res, tmp)
			return
		} else if target < 0 {
			return
		}

		for i := index; i < len(candidates); i++ {
			// 树层去重
			if i > index && candidates[i] == candidates[i-1] {
				continue
			}

			list = append(list, candidates[i])
			helper(target-candidates[i], i+1) // 树枝去重
			list = list[:len(list)-1]
		}
	}
	helper(target, 0)
	return res
}

// 实现方式2
func combinationSum2V2(candidates []int, target int) [][]int {
	var res [][]int
	var list []int
	var helper func(target int, index int)
	used := make(map[int]bool)
	sort.Ints(candidates)
	helper = func(target int, index int) {
		if target == 0 {
			tmp := make([]int, len(list))
			copy(tmp, list)
			res = append(res, tmp)
			return
		} else if target < 0 {
			return
		}

		for i := index; i < len(candidates); i++ {
			// 树层去重
			if i > index && candidates[i] == candidates[i-1] && !used[i-1] {
				continue
			}

			used[i] = true
			list = append(list, candidates[i])
			helper(target-candidates[i], i+1) // 树枝去重
			list = list[:len(list)-1]
			used[i] = false
		}
	}
	helper(target, 0)
	return res
}
